The present invention is directed to communications networks. It particularly concerns congestion avoidance.
Internetwork communications are based on operations of routers, which are network devices that determine, on the basis of destination information in packets that they receive, where to forward the packets so that they are likely to reach the intended destinations.
Router configurations vary widely, but that of FIG. 1 is typical. Router 10 includes a plurality of communications interfaces 12, 14, and 16, which send and receive communications packets to and from remote locations. When one of the interface modules receives an incoming packet from a remote location, it places header information from that packet onto an internal communications bus 18 by which it communicates with a forwarding engine 20 that determines where the packet should be sent. The interfaces and forwarding engine can be implemented in respective high-performance processors 21 and storage circuitry 22 that contains program instructions that configure the processors to act together as a router. The programming for such implementations is typically provided in some type of persistent medium, such as a magnetic disk or semiconductor read-only memory. That type of implementation most often executes that programming after it has been transferred to a volatile medium, such as dynamic or static random-access memory. The drawing shows the storage circuitry 22 as separate media for each interface or forwarding engine, but some configurations may additionally, or instead, employ common storage. In some cases the router's programming may be updated remotely by sending it electrical or other signals that represent the instructions.
To maximize speed capacity, other routers are implemented wholly or largely in “random logic” instead of general-purpose processors. The “programming” in such implementations is ordinarily hard-coded in the circuitry's structure, but read-only or read/write storage media may be employed in such implementations, too, to affect the router's behavior. Once the decision has been made, an output packet is formed from the input packet by packet-assembly circuitry that may reside in one or more of the interface modules and/or the forwarding engine, and the forwarding engine causes another interface to send the output packet to a further remote location.
Some routers may actually be implemented in switches that employ the Asynchronous Transfer Mode (ATM) protocol. Such switches operate in the manner that FIG. 2 depicts. Suppose that one of router 10's ATM interfaces provides communication with another router 24, while a different ATM interface provides communication with a further router 26. Suppose further that router 10 is an “edge router” of an internet-service provider: although it is part of a network that is maintained by the service provider, it has direct links to client routers such as router 26, which are outside the service-provider network.
Router 26 sends information in packets to router 10, and we will assume for present purposes that the packets sent by router 26 conform to the Internet Protocol (IP). In accordance with that protocol, each packet begins with a header that includes, among other information, an address that indicates the host system to which the packet should ultimately be routed. Router 10 includes storage circuitry containing a routing table that tells the router the direction in which to send the packet so that it will reach the destination set forth in the IP header.
Now, the service provider must of necessity base its initial routing decision on the incoming packet's destination address. But IP addressing makes doing so in the conventional manner a relatively time-consuming process. An IP address is typically 32 bits long: it could theoretically distinguish over four billion host systems. Although the number of host systems that have globally unique IP addresses is much smaller than this, the actual number of such systems is considerably greater than the number of entries it is practical for an individual router's forwarding table to include.
Many of the forwarding table's entries therefore are directed not to a single host address but rather to a “prefix” of fewer than the thirty-two bits. Such an entry indicates that the forwarding information contained in it can be used to reach any destination address that begins with the prefix to which the entry is directed. Prefixes vary in length, the longest being the most specific and thus presumably representing the best routes to the included host addresses. So a router that receives an IP packet searches through its forwarding table to find the longest prefix that matches the incoming packet's destination address, and it forwards the packet in accordance with the information thus found.
Such longest-match searches are time-consuming. But an Internet-service provider's “transit” routers, i.e., those that are not edge routers, can avoid such an expensive longest-match search if they forward the packets in ATM “cells.” An ATM cell includes a “virtual-channel identifier,” which identifies the receiving router's forwarding-table entry that contains the forwarding information for the “virtual channel” along which the cell is to be forwarded. For this purpose, an edge router such as router 10 works with other routers to set up a virtual channel within the service-provider network before it forwards the first packet to a particular destination. That is, successive routers determine the path through the network that such packets should take, and they tell each other where in their respective forwarding tables they keep forwarding information for that virtual circuit.
FIG. 3 depicts the format that ATM switches use to send information over the resultant virtual channel. From the point of view of an ATM client, the frame that FIG. 3's third row depicts is the basic transmission unit. (Those skilled in the art will recognize that there are also other possible ATM frame formats, but FIG. 6's third row depicts one, known as “AAL5,” that would typically be employed for user data.) Since the service-provider network is being used to forward IP datagrams from router 26, that drawing's fourth row depicts the frame's payload as an IP datagram having the usual IP header and IP data.
From the point of view of such an ATM switch, though, the (variable-length) third-row frame is not the basic transmission unit. Specifically, the edge router divides that frame into pieces that it forwards in a plurality of equal-sized cells. As FIG. 3's second row shows, an ATM cell consists of a cell payload and header. FIG. 3's first row depicts the cell's header format and shows that it includes a PTI field. One purpose of the PTI field is to indicate whether the cell containing it is the last one in a frame. If it is, then the cell's last eight bytes form the frame trailer field depicted in FIG. 3's third row. Among other things, the trailer indicates how much of the preceding cell's contents is not actual frame payload but instead is fill used to pad the cell to the predetermined ATM cell size.
The header field of particular interest here is the VPI/VCI field. Each switch associates a virtual path or virtual channel with a virtual-path or virtual-channel identifier of local significance to that switch: it indicates the forwarding-table entry from which the switch is to fetch forwarding information for the cell being forwarded. Part of that entry's information is a replacement for the incoming cell's virtual-path or virtual-channel identifier. The replacement specifies the virtual path or virtual channel's correct entry in the forwarding table of the “next-hop” switch, to which the current switch's forwarding-table entry directs that the cell be sent.
Suppose that the client router 26 of FIG. 2 sends edge router 10 a packet whose IP destination address is D1. Also suppose that a further client router 28 provides access to that destination. The service-provider router having a direct link to client router 28 is router 30. To forward the packet properly, the provider network sets up an ATM virtual path from router 10 through routers 24 and 32 to router 30. Router 10 then divides packets specifying destination D1 into ATM cells, and it places into each such cell's header the virtual-path identifier V1 that router 10 learned during the virtual-channel-establishment process was the location in router 24's forwarding table where router 24 stored the proper forwarding information for the virtual channel to router 30. So router 24 does not need to perform a longest-match search when it receives such cells: it goes directly to the table entry that virtual-path identifier V1 specifies, and that entry tells it both the interface over which to forward the cell and the virtual-channel identifier V2 with which it should replace the incoming cell's virtual-channel identifier V1.
Similarly, router 32 employs virtual-channel identifier V2 to find its forwarding-table entry for that virtual channel. That entry tells router 32 to forward the cell over its interface with the link to router 30 and to place the value V3 into that cell's VPI/VCI field. Since router 30 is an edge router and must forward the packet to a non-ATM router 28, it assembles the IP-packet-containing frame from its constituent cells and forwards that IP packet, which still contains its destination address D1 to client router 28.
A similar sequence of events occurs when another customer router 34 sends an IP datagram containing destination address D1 to another edge router 36. As before, each of the routers along the service provider's path toward destination D1 allocates a virtual-channel identifier to that virtual channel. Edge router 36 encapsulates the datagram in an ATM frame and divides the frame into fixed-length cells whose virtual-channel identifier is, say, V4. Subsequent routers 40 and 32 forward such cells, replacing their virtual-channel identifiers with values V5 and V6, respectively. And, as before, the egress edge router 30 re-assembles the IP datagram and sends it to the customer router 28 that can forward it on to its ultimate destination.
Note that routers 30 and 32 in this scenario allocate two different virtual-channel identifiers to a common-destination path; they do not “merge” the channels by assigning a common virtual-channel identifier. This scenario is typical, even though virtual-channel identifiers are a relatively scarce resource in ATM switches.